package algorithmTopics.graph;

import java.util.*;

/**
 * 解决方案
 *
 * @author 86155
 * @date 2025/07/16
 */
public class Solution {
    /**
     * 课程表
     *
     * @param numCourses    需要修读的课程
     * @param prerequisites 先决条件
     * @return boolean 是否可以修读玩课程
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 每个节点入度
        int[] indegrees = new int[numCourses];
        // 存储每个节点的前置节点 表示相邻节点
        List<List<Integer>> adjacency = new ArrayList<>();
        // 初始化
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }
        for (int[] i : prerequisites) {
            indegrees[i[0]]++;
            adjacency.get(i[1]).add(i[0]);
        }

        Queue<Integer> queue = new LinkedList<>();
        //入度为0 的课程装载 表示现在可以开始学习
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.add(i);
            }
        }
        //BFS 拓扑排序
        while (!queue.isEmpty()) {
            //入度为0的课程
            int pre = queue.poll();
            numCourses--;
            // 依赖于他的课程
            for (int cur : adjacency.get(pre)) {
                // 减少
                indegrees[cur]--;
                if (indegrees[cur] == 0) {
                    queue.add(cur);
                }
            }
        }

        return numCourses == 0;

    }

    /**
     * 橘子腐烂
     *
     * @param grid 网格
     * @return int -1：不可能全部腐烂；其他数字：全部腐烂需要的分钟数
     */
    public int orangesRotting(int[][] grid) {
        //
        int m = grid.length;
        int n = grid[0].length;
        // 新鲜橘子个数
        int good = 0;
        Queue<int[]> badLocation = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    good++;
                } else if (grid[i][j] == 2) {
                    badLocation.add(new int[]{i, j});
                }
            }
        }
        // 需要的分钟数
        int min = 0;
        while (good != 0 && !badLocation.isEmpty()) {
            int len = badLocation.size();
            min++;
            for (int i = 0; i < len; i++) {
                int[] location = badLocation.poll();
                int x = location[0];
                int y = location[1];
                if (x + 1 < m && grid[x + 1][y] == 1) {
                    grid[x + 1][y] = 2;
                    badLocation.add(new int[]{x + 1, y});
                    good--;
                }
                if (x - 1 >=0  && grid[x - 1][y] == 1) {
                    grid[x - 1][y] = 2;
                    badLocation.add(new int[]{x - 1, y});
                    good--;
                }
                if (y + 1 < n && grid[x][y + 1] == 1) {
                    grid[x][y + 1] = 2;
                    badLocation.add(new int[]{x, y + 1});
                    good--;
                }
                if (y - 1 >= 0  && grid[x][y - 1] == 1) {
                    grid[x][y - 1] = 2;
                    badLocation.add(new int[]{x, y - 1});
                    good--;
                }
            }
        }

        return good == 0 ? min : -1;
    }

    private boolean orangesRottingHelper(int[][] grid, int x, int y, int xLen, int yLen) {
        boolean isChange = false;
        //把上下左右 的好橘子 变坏
        if (x + 1 < xLen && grid[x + 1][y] == 1) {
            grid[x + 1][y] = 2;
            isChange = true;
        }
        if (x - 1 >= 0 && grid[x - 1][y] == 1) {
            grid[x - 1][y] = 2;
            isChange = true;
        }
        if (y + 1 < yLen && grid[x][y + 1] == 1) {
            grid[x][y + 1] = 2;
            isChange = true;
        }
        if (y - 1 >= 0 && grid[x][y - 1] == 1) {
            grid[x][y - 1] = 2;
            isChange = true;
        }
        return isChange;
    }

    /**
     * num群岛
     *
     * @param grid 一片区域
     * @return int 岛屿个数
     */
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 1 搜索是否有连着的岛屿
                // dfs 把岛屿搜索过的岛屿变成 0
                if (grid[i][j] == '1') {
                    numIslandsHelper(grid, i, j, grid.length - 1, grid[0].length - 1);
                    res++;
                }
            }
        }
        return res;
    }

    private void numIslandsHelper(char[][] grid, int x, int y, int xLen, int yLen) {
        //负责把连着的岛屿 找出来
        if (x < 0 || x > xLen || y < 0 || y > yLen || grid[x][y] == '0') {
            return;
        }
        //标记为水域
        grid[x][y] = '0';
        numIslandsHelper(grid, x + 1, y, xLen, yLen);
        numIslandsHelper(grid, x - 1, y, xLen, yLen);
        numIslandsHelper(grid, x, y + 1, xLen, yLen);
        numIslandsHelper(grid, x, y - 1, xLen, yLen);
    }


}
